#ifndef AER_BVH_HPP_
#define AER_BVH_HPP_

#include "../aerDefs.hpp"

#include <vector>
#include "../aerMesh.hpp"
#include "../aerBoundingBox.hpp"
#include "../view/aerFrustum.hpp"//

#include "../aerIntersection.hpp"// temp


namespace aer {

/// ===========================================================
/// + Bounding Volume Hierarchy using Surface Area Heuristics +
/// ===========================================================
class BVH
{
  // ================
  // ++ STRUCTURES ++
  // ================
  public:
    struct Node
    {
      unsigned int id;          // node id
      unsigned int parent;      // parent id
      unsigned int offset_flag; // bits 0..30 : offset to first child OR leafId
                                // bits 31    : flag wether the node is a leaf
      
      
      Node() : id(0u), parent(0u), offset_flag(0u) {}
      
      void set(unsigned int nodeId, unsigned int parentId, unsigned int offset,
               bool bIsALeaf)
      {
        id = nodeId;
        parent = parentId;
        offset_flag = offset & (0x7FFFFFFF);        
        if (bIsALeaf) offset_flag |= (unsigned int)(1<<31);
      }
    };
    
    struct NodeAttrib
    {
      BoundingBox aabb;
      unsigned char failPlaneId;
      NodeAttrib() : failPlaneId(0u) {}
    };
  

  private:    
    /// Maps common buffers for the building process
    struct BuildParams
    {
      unsigned int *pIndices[3];      // per-axis sorted indices
      unsigned int *pLUT;             // Use to resort pIndices
      
      BuildParams(unsigned int *pSortedX,
                  unsigned int *pSortedY,
                  unsigned int *pSortedZ,
                  unsigned int *pLUT)
        : pLUT(pLUT)
      {
        pIndices[0] = pSortedX;
        pIndices[1] = pSortedY;
        pIndices[2] = pSortedZ;
      } 
    };
    

  // ============
  // ++ FIELDS ++
  // ============    
  protected:
    unsigned int m_numNodes;
    unsigned int m_numLeaves;
    
    // ++ Nodes attribs ++
    std::vector<Node> m_tree;
    std::vector<NodeAttrib> m_attribs;
    
    // ++ Leaves attribs ++
    const Mesh *m_pMeshes;//
    const BoundingBox *m_pBoundingBoxes; // mapped leaves' AABBs (/ objects)


  // ====================
  // ++ STATIC METHODS ++
  // ====================
  protected:  // ~
    static bool IsALeaf(const Node &n) {
      return n.offset_flag & (unsigned int)(1<<31);
    }
    
    static unsigned int GetNodeOffset(const Node &n) {
      return (n.offset_flag & (0x7FFFFFFF));
    }
    
  
  // =============
  // ++ METHODS ++
  // =============
  public:
    BVH();
    
    void build(const size_t nElems, const Mesh *pMeshes, const BoundingBox *pBoundingBoxes);
        
    void release() {/*empty*/}
    
    //xxx temp [debug]
    void display(glm::vec4 planes[Frustum::kNumPlane], Node *node=0, unsigned int depth=0);
    

  protected:
    virtual void init() {}
    
    bool isInsideViewFrustum(const unsigned int nodeId, 
                             const glm::vec4 planes[Frustum::kNumPlane])
    {
      NodeAttrib& n = m_attribs[nodeId];
      return intersectFrustumAABB( planes, n.aabb, &n.failPlaneId) != OUTSIDE;
    }
    
  private:
    void subBuild(const unsigned int nodeId, 
                  const unsigned int parentId, 
                  unsigned int *pIdCounter,
                  const BuildParams &params, 
                  const size_t offset, 
                  const size_t count);
    
    bool findBestSACost(const BuildParams &params, 
                        const size_t offset, 
                        const size_t count, 
                        const unsigned char axis, 
                        float *pBestCost, 
                        unsigned int *pBestId);
    
    void resort(const BuildParams &params,
                const size_t offset, 
                const size_t count,
                const unsigned char baseAxis, 
                const unsigned char axis, 
                const unsigned int splitIdx);
    
};

} // aer

#endif //AER_BVH_HPP_
